To satisfy demands for wireless data traffic, which have been increasing since commercialization of a 4th generation (4G) communication system, efforts have been made to develop an improved 5th generation (5G) or pre-5G communication system. That is why the 5G or pre-5G communication system is called a beyond 4G network communication system or a post long term evolution (LTE) system.
To achieve high data rates, deployment of the 5G communication system in a millimeter wave (mmWave) band (for example, a 60-GHz band) is under consideration. In order to mitigate propagation path loss and increase a propagation distance in the mmWave band, beamforming, massive multiple input multiple output (MIMO), full dimensional MIMO (FD-MIMO), array antenna, analog beamforming, and large-scale antenna technology have been discussed for the 5G communication system.
Further, to improve a system network, techniques such as evolved small cell, advanced small cell, cloud radio access network (cloud RAN), ultra-dense network, device-to-device (D2D) communication, wireless backhaul, moving network, cooperative communication, coordinated multi-point (CoMP), and received interference cancelation have been developed for the 5G communication system.
Besides, advanced coding modulation (ACM) techniques, such as hybrid frequency shift keying (FSK) and quadrature amplitude modulation (QAM) modulation (FQAM) and sliding window superposition coding (SWSC), and advanced access techniques, such as filter bank multi carrier (FBMC) and non-orthogonal multiple access (NOMA), and sparse code multiple access (SCMA) have been developed for the 5G communication system.
In a communication or broadcasting system, link performance may be degraded greatly by noise, fading, and inter-symbol interference (ISI). Accordingly, a technique for overcoming noise, fading, and ISI is required to implement high-speed digital communication or broadcasting systems that require high data throughput and high reliability, such as future-generation mobile communication, digital broadcasting, and portable Internet. To overcome noise, error correction codes have recently been studied actively as a method for increasing communication reliability by efficiently recovering information distortion.
Low density parity check (LDPC) codes were originally developed by Gallager in 1960s and largely ignored for a long time because their computational complexity was too high for the hardware technology at the time. However, in 1993, turbo codes developed by Berrou, Glavieux, and Thitimajshima were the first codes to be shown to perform close to the Shannon limit or channel capacity. Along with many interpretations regarding the performance and characteristics of turbo codes, extensive research was made on iterative decoding and graph-based channel encoding. The success of turbo codes led to the rediscovery of LDPC codes in the late 1990s. It was revealed that iterative decoding using a sum-product algorithm on a Tanner graph representing an LDPC code performs close to the Shannon limit.
Although an LDPC code is generally defined by a party heck matrix, a bipartite graph known as a Tanner graph may be used to represent the LDPC code.
FIG. 1 is a view illustrating a structure of a systematic LDPC codeword according to the related art.
Referring to FIG. 1, the systematic LDPC codeword will be described below.
An LDPC codeword 100 including Nldpc bits or symbols is generated by LDPC-encoding a received information word 102 including Kldpc bits or symbols. For convenience of description, it is assumed that for the input of the information word 102 including Kldpc bits or symbols, the codeword 100 including Nldpc bits or symbols is generated. For example, LDPC encoding of the information word 102 including Kldpc bits, I=[i0, i1, i2, . . . iKldpc−1] results in the codeword 100, c=[c0, c1, c2 . . . cNldpc−1]. For example, a codeword is a bit stream including a plurality of bits, and a codeword bit is bit of the codeword. Further, an information word is a bit stream including a plurality of bits, and an information word bit is a bit of the information word. In the case of a systematic code, the codeword 100 is given as c=[c0, c1, c2, . . . cNldpc−1]=[i0, i1, i2, . . . iKldpc−1, p0, p1, p2, . . . pNldpc−Kldpc−1] where P=[p0, p1, p2 . . . pNldpc−Kldpc−1] represents parity bits 104. The number of parity bits 104, Nparity may be calculated by Nparity=Nldpc−Kldpc.
An LDPC code is a form of linear block code, and LDPC encoding involves determining a codeword satisfying the condition described by Equation 1.
                                          H            ·                          c              T                                =                                                    [                                                                                                    h                        0                                                                                                            h                        1                                                                                                            h                        2                                                                                    …                                                                                      h                                                                              N                            ldpc                                                    -                          1                                                                                                                    ]                            ·                              c                T                                      =                                                            ∑                                      i                    =                    0                                                        N                    ldpc                                                  ⁢                                                      c                    i                                    ·                                      h                    i                                                              =              0                                      ,                            Equation        ⁢                                  ⁢        1                                                          ⁢                  Here          ,                                          ⁢                                          ⁢                      c            =                          [                                                                                                                  c                        0                                            ,                                                                                                                          c                        1                                            ,                                                                                                                          c                        2                                            ,                      …                      ⁢                                                                                          ,                                                                                                  c                                                                        N                          ldpc                                                -                        1                                                                                                        ]                                                                      
In Equation 1, H is a parity check matrix, C is a codeword, c, is an ith bit of the codeword C, and Nldpc is the length of the LDPC codeword. Herein, hi is an ith column of the parity check matrix H.
The parity check matrix H includes as many columns as the number of bits of the LDPC codeword, that is, Nldpc columns. According to Equation 1, the sum of the products between the columns hi and the codeword bits ci is ‘0’, which means that each ith column hi is related to each ith codeword bit ci.
With reference to FIG. 2, a graph representation of an LDPC code will be described.
FIG. 2 illustrates a parity check matrix H1 with 4 rows by 8 columns, and a Tanner graph representing the parity check matrix H1 according to the related art.
Referring to FIG. 2, since the parity check matrix H1 includes 8 columns, a codeword of length 8 is generated. A code generated from the parity check matrix H1 is an LDPC code, and the columns correspond to 8 coded bits.
Referring to FIG. 2, the Tanner graph representing the LDPC code for encoding and decoding based on the parity check matrix H1 includes eight variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216 and four check nodes 218, 220, 222 and 224. An ith column and a jth row in the parity-check matrix H1 represent a variable node xi and a jth check node, respectively. If an entry at the ith column and the jth row in the parity-check matrix H1 is one, i.e., non-zero, this means that an edge is drawn between the variable node xi and the jth check node on the Tanner graph illustrated in FIG. 2.
The degree of a variable node or a check node on the Tanner graph of the LDPC code is the number of edges connected to the node. The degree of a node is equal to the number of non-zero entries in a column or row corresponding to the node in the parity-check matrix of the LDPC code. For example, the degrees of the variable nodes x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214, and x8 216 are 4, 3, 3, 3, 2, 2, 2 and 2, respectively, and the degrees of the check nodes 218, 220, 222 and 224 are 6, 5, 5 and 5, respectively. Similarly, the numbers of non-zeroes in the columns of the parity-check matrix HI of FIG. 2, corresponding to the variable nodes of FIG. 2 are 4, 3, 3, 3, 2, 2, 2 and 2, respectively, and the numbers of non-zeroes in the rows of the parity-check matrix of FIG. 2, corresponding to the check nodes of FIG. 2 are 6, 5, 5 and 5, respectively.
The LDPC code may be decoded using an iterative decoding algorithm based on a sum-product algorithm on the bipartite graph illustrated in FIG. 2. The sum-product algorithm is a form of message passing algorithm in which messages are exchanged through an edge on a bipartite graph, and an output message is calculated and updated from messages input to a variable node or a check node.
The value of an ith coded bit may be determined based on a message of an ith variable node. The value of the ith coded bit may be determined by either of hard decision and soft decision. Accordingly, the performance of the ith bit, ci of the LDPC code corresponds to the performance of the ith variable node of the Tanner graph. The performance may be determined according to the positions and number of ones in the ith column of the parity check matrix. In other words, the performance of Nldpc codeword bits of a codeword may depend on the positions and number of ones in the parity check matrix, which means that the performance of the LDPC code is affected significantly by the parity check matrix. Therefore, to design an LDPC code with excellent performance, there is a need for a method for designing a good parity check matrix.
For implementation simplicity, a communication or broadcasting system generally adopts a quasi-cyclic LDPC (QC-LDPC) code using a QC parity check matrix.
A QC-LDPC code characteristically has a parity check matrix including zero matrices or circulant permutation matrices, which are small square matrices.
A detailed description will be given of a QC-LDPC code.
First, an L×L circulant permutation matrix P=(Pi,j) is defined as Equation 2. Pi,j represents an entry in an ith row and a jth column of the matrix P (0≤i, j<L).
                              P                      i            ,            j                          =                  {                                                                      1                                                                                                                    if                        ⁢                                                                                                  ⁢                        i                                            +                      1                                        ≡                                          j                      ⁢                                                                                          ⁢                      mod                      ⁢                                                                                          ⁢                      L                                                                                                                    0                                                  otherwise                                                      .                                              Equation        ⁢                                  ⁢        2            
For the permutation matrix P as defined above, Pi (0≤i<L) is a circulant permutation matrix obtained by cyclically shifting the elements of an L×L identity matrix to the right by i positions.
The simplest parity check matrix H of a QC-LDPC code may be represented as Equation 3.
                    H        =                  [                                                                      P                                      a                    11                                                                                                P                                      a                    12                                                                              …                                                              P                                      a                                          1                      ⁢                      n                                                                                                                                            P                                      a                    21                                                                                                P                                      a                    22                                                                              …                                                              P                                      a                                          2                      ⁢                      n                                                                                                                          ⋮                                            ⋮                                            ⋱                                            ⋮                                                                                      P                                      a                                          m                      ⁢                                                                                          ⁢                      1                                                                                                                    P                                      a                                          m                      ⁢                                                                                          ⁢                      2                                                                                                  …                                                              P                                      a                    mn                                                                                ]                                    Equation        ⁢                                  ⁢        3            
Let P−1 be defined as an L×L zero matrix. The exponent ai,j of each circulant permutation matrix or zero matrix in Equation 3 has one of the values of {−1, 0, 1, 2, . . . , L−1}. The parity check matrix H described in Equation 3 has m row blocks by n column blocks, and thus its size is mL×nL.
If the parity check matrix of Equation 3 is of full rank, the size of the information word bits of the QC-LDPC code corresponding to the parity check matrix is obviously (n−m)L. For convenience of description, (n−m) column blocks corresponding to the information word bits are referred to as information word column blocks, and m column blocks corresponding to the other parity bits are referred to as parity column blocks.
In general, an m×n binary matrix produced by replacing each circulant permutation matrix and each zero matrix by one and zero, respectively in the parity check matrix of Equation 3 is called a mother matrix M(H) of the parity check matrix H, and an m×n integer matrix produced by selecting the exponent of each circulant permutation matrix or zero matrix is called an exponent matrix E(H) of the parity check matrix H, as expressed as Equation 4.
                              E          ⁡                      (            H            )                          =                  [                                                                      a                  11                                                                              a                  12                                                            …                                                              a                                      1                    ⁢                    n                                                                                                                        a                  21                                                                              a                  22                                                            …                                                              a                                      2                    ⁢                    n                                                                                                      ⋮                                            ⋮                                            ⋱                                            ⋮                                                                                      a                                      m                    ⁢                                                                                  ⁢                    1                                                                                                a                                      m                    ⁢                                                                                  ⁢                    2                                                                              …                                                              a                  mn                                                              ]                                    Equation        ⁢                                  ⁢        4            
Meanwhile, the performance of an LDPC code may be determined according to its parity check matrix. Therefore, it is necessary to design a proper parity check matrix for an LDPC code with excellent performance. Further, an LDPC encoding or decoding method supporting various input lengths and code rates is required.
Lifting is used to efficiently design a QC-LDPC code. The lifting is a technique of efficiently designing a very large parity check matrix by setting L determining the size of a circulant permutation matrix or zero matrix from a given small mother matrix in a specific rule. A lifting scheme of the related art and the characteristics of a QC-LDPC code designed in the lifting scheme of the related art are summarized as follows.
Given an LDPC code C0, let S QC-LDPC codes to be designed by lifting be denoted by C1, . . . , CS and the size of row and column blocks of each of the QC-LDPC codes be denoted by Lk. The LDPC code C0 is the smallest LDPC code having the mother matrices of the LDPC codes C1, . . . , CS as a parity check matrix, and the size L0 of row and column block of the LDPC code C0 is 1. For convenience of description, the parity check matrix Hk of each code Ck includes an m×n exponent matrix E(Hk)=(ei,j(k)) where each exponent ei,j(k) has a value selected from the values of {−1, 0, 1, 2, . . . , Lk−1}.
Lifting is performed in the order of C0→C1→ . . . →CS and characterized by L(k+1)=q(k+1)Lk (q(k+1) is a positive integer, k=0, 1, . . . , S−1). In view of the nature of lifting, once a parity check matrix HS of a code Cs is stored, all of the QC-LDPC codes C0, C1, . . . , CS may be represented according to the lifting scheme by Equation 5.
                              E          ⁡                      (                          H              k                        )                          ≡                  ⌊                                                    L                k                                            L                S                                      ⁢                          E              ⁡                              (                                  H                  S                                )                                              ⌋                                    Equation        ⁢                                  ⁢        5            OrE(Hk)≡E(Hs) mod Lk  Equation 6
In the lifting scheme described by Equation 5 or Equation 6, since Lk values being row block sizes or column block sizes of the parity check matrices of the QC-LDPC codes Ck are in a multiple relationship, the exponent matrices are also selected in a specific method. This lifting scheme of the related art facilitates designing of a QC-LDPC code with improved error floor characteristics, because the algebraic or graph characteristics of each parity check matrix designed by lifting are improved.
However, a shortcoming with the lifting scheme of the related art is that the length of each code is limited greatly because of the multiple relationship between the Lk values. For example, it is assumed that a minimum lifting scheme, such as L(k+1)=2*Lk is applied to each value of Lk. In this case, the size of the parity check matrix of each QC-LDPC code may be 2km×2kn. For example, if lifting is applied at 10 levels (S=10), 10 sizes may result.
For the above reason, the lifting scheme of the related art is not viable in designing a QC-LDPC code supporting various lengths. However, a typical communication system requires very high-level length compatibility in consideration of transmission of various types of data. As a result, it is difficult to apply an LDPC code to the communication system in the method of the related art.
Therefore, a need exists for a method and an apparatus for LDPC encoding and decoding, which support various input lengths and various code rates.
The above information is presented as background information only to assist with an understanding of the present disclosure. No determination has been made, and no assertion is made, as to whether any of the above might be applicable as prior art with regard to the present disclosure.